1. Field of the Invention
The present invention relates to an image encoding method and apparatus, and more particularly, to reversible encryption for multi-valued images.
2. Description of the Related Art
Full color images generally have a great amount of data. For example, four-color full color images of 300 SPI (spot per inch), A4 size have a data quantity of about 32 MB. Accordingly, when images are accumulated or transmitted, image compression may be used. A memory capacity required for accumulation and time required for transmission can be reduced by image compression, whereas since the image compression itself applies complex processing to an entire image, image compression by software has been time-consuming. Although hardware dedicated to image compression may be used to reduce the time, adding the hardware has been costly.
For example, in nonreversible encryption called a base line process defined in JPEG (Joint Photographic Expert Group), which is a standard of image encryption, an image is divided into blocks, each with eight pixels wide and eight pixels long, transformation called DCT (Discrete Cosine Transform) is applied to each block, a block image is transformed into frequency components before being quantized, and finally Huffman encoding is performed. FIG. 1 shows an example of a block diagram of an apparatus that performs compression using the JPEG method.
That is, in the example of FIG. 1, an image input unit 10 divides an image into blocks, each with eight pixels wide and eight pixels long, and a DCT transformation unit 11 subjects the image of each block to DCT transformation. A quantization unit 12 quantizes the DCT transformation data for each DCT coefficient using a quantization matrix to compress high-frequency components. Furthermore, an encoding unit 13 subjects the quantized data to entropy encoding (Huffman encoding) and outputs a result from a code output unit 14.
Since DCT performs two eight-by-eight matrix multiplications and quantization is achieved by divisions among elements of the matrix, to process one pixel of one color requires 16 multiplications, 14 additions, and one division. An entire image of 300 SPI, which contains about eight million pixels of four colors, requires a total of about five hundred and twelve million multiplications, four hundred and forty-eight million additions, and thirty-two million divisions. With Huffman encoding, image reading, and other overheads further added, one or more minutes have been required to compress a full color image of 300 SPI, A4 size even by the use of the most advanced workstation.
On the other hand, with general-purpose data compression methods such as LZW (Lempel-Ziv-Welch), the use of a complex compression method using dictionaries provides no significant improvement in processing time and leads to a low compression rate.
A prediction encoding system enables compression with a relatively small amount of computation. There is disclosed in e.g., Japanese Published Unexamined Patent Application No. Hei 9-200774, an apparatus that uses the values of a plurality of surrounding pixels as prediction values to perform reversible encoding by using information for identifying a prediction part outputting the smallest prediction error and the prediction error. FIG. 2 shows the configuration of the apparatus.
This apparatus comprises: a plurality of prediction units 20 that predict the value of a target pixel from the values of pixels around it on the basis of respectively different parameters; prediction error calculation units 21 that calculate differences (prediction errors) between prediction values obtained by the plurality of prediction units 20 and the value of target pixel; a prediction selection unit 22 that selects a prediction unit on the basis of the magnitude of the prediction errors and priority; a priority setting unit 23 that sets priority for each of the plurality of prediction units; and an encoding unit 24 that encodes the value of target pixel on the basis of a prediction value obtained by the selected prediction unit. The priority setting unit 23 determines the order of selection on the basis of selection history. The prediction selection unit 22 comprises: a minimum prediction error detection unit 221; a first multiplexer 222 that selectively outputs a prediction unit on the basis of a minimum prediction error and priority set by the priority setting unit 23; a latch unit 223 that latches selective output; and a second multiplexer 224 that outputs prediction errors supplied from the prediction units 20 on the basis of selective output from the latch unit 223. The prediction unit 20 performs prediction using the values of left, upper, and other pixels, as shown in FIG. 3.
This apparatus, which uses pixels around a target pixel or the average of them as a prediction method, requires no multiplication and division for pixel values. However, multiple prediction units must be used to obtain a high compression rate, and prediction and error calculation, selection of a prediction unit to give a minimum error, and determination of priority of predictors are performed for each pixel. Therefore, implementing this compression apparatus by software would require much time for compression.
There is disclosed in Japanese Published Unexamined Patent Application No. Hei 9-224253 an apparatus that reversibly compresses images produced in computer graphics and page description language (PDL) processing systems.
This apparatus comprises: an image input part that inputs images; a plurality of pixel value prediction parts that predict the pixel values of a plurality of pixels to be encoded within an image inputted by the image input part by respectively different prediction methods; a prediction error calculation part that calculates an error between the value of a target pixel within the image inputted by the image input part and a prediction value predicted by a predetermined prediction method; a match determination part that determines whether or not prediction values predicted by the plurality of pixel value prediction parts match the value of a target pixel; a selection part that alternatively outputs, on the basis of the determination output of the match determination part, identification information for identifying a pixel value prediction part whose prediction value is determined matching by the match determination part and an error calculated by the prediction error calculation part; an encoding part that encodes the identification information and the error outputted by the selection part; and an output part that output codes encoded by the encoding part.
FIG. 4 is a block diagram showing the configuration of this apparatus.
In FIG. 4, image data 34 is supplied from an image input unit 30 to a first prediction unit 31, a second prediction unit 32, and a prediction error calculation unit 33. The first prediction unit 31 and the second prediction unit 32 each predict the pixel value of a target pixel on the basis of the image data 34 by a predetermined method and outputs it to a selection unit 37 as prediction value data 35. The prediction error calculation unit 33 predicts the pixel value of the target pixel on the basis of the image 34 by a predetermined method, subtracts the predicted value from the actual pixel value of the target pixel, and outputs a result to the selection unit 37 as prediction error data 36.
The selection unit 37 determines from the image data 34 and the prediction value data 35 whether the prediction on the target pixel is correct or incorrect. As a result, the identification number of a prediction unit that made prediction correctly, if any, is outputted to the encoding unit 39; if there is no prediction unit that made prediction correctly, the prediction error data 36 is converted into prediction status data 38 before being sent to an encoding unit 39.
The encoding unit 39 uses a predetermined encoding method to encode the identification number 35 of the prediction unit or the prediction error data 36, and sends a result to a code output unit 41 as code data 40. The code output unit 41 outputs the code data 40 to the outside as output codes.
Here, the prediction units perform prediction using the pixel values of immediately left and immediately upper pixels and the like with respect to a target pixel, as shown in FIG. 5.
FIGS. 6 and 7 show the operation of the apparatus. FIG. 6 shows the whole of prediction encoding processing and FIG. 7 shows details of selection processing of the prediction units. The contents of the operation will not be described because they can be easily understood from the figure.
The apparatus does not require multiplications and divisions for pixel values because it uses pixels around a target pixel as a prediction method. This apparatus also has an advantage that a high compression rate is obtained for images produced by computer graphics or the like. Furthermore, since an error is calculated only once only when a prediction value and the value of a target pixel do not match, computational complexity at software configuration is somewhat less than with the apparatus described in Japanese Published Unexamined Patent Application No. Hei 9-200774.
However, the apparatus must also use many prediction units to obtain a high compression ratio, and if the compression apparatus is implemented by software, processing shown in FIGS. 6 and 7 is performed. In other words, since prediction by each prediction unit, match determination, and error calculation are performed for each pixel, a great deal of time is required for compression when these processes are implemented by software. For example, about 30 seconds are required to compress a full color image of 300 SPI, A4 size.